package main

import "fmt"

// 链表节点
type SinglyLinkedListNode struct {
	data     any                   // 存储数据
	nextNode *SinglyLinkedListNode // 存储下一个节点指针
}

// 在头部插入节点
func SinglyLinkedListUnShift(singlyLinkedList *SinglyLinkedListNode, data any) *SinglyLinkedListNode {
	// 初始化一个节点
	node := &SinglyLinkedListNode{data: data}
	// 直接将上述节点的下一个节点指向之前的头节点即可
	node.nextNode = singlyLinkedList
	return node
}

// 在尾部插入节点
func SinglyLinkedListPush(singlyLinkedList *SinglyLinkedListNode, data any) *SinglyLinkedListNode {
	// 初始化一个节点
	node := &SinglyLinkedListNode{data: data}
	// 如果头节点不存在则直接将上述节点返回
	if singlyLinkedList == nil {
		return node
	}
	// 如果头节点的下一个节点为空，那么直接将头节点的下一个节点指向上述节点
	if singlyLinkedList.nextNode == nil {
		singlyLinkedList.nextNode = node
		return singlyLinkedList
	}
	// 否则遍历找到最后一个节点，将最后一个节点的下一个节点指向上述节点
	curNode := singlyLinkedList
	for curNode.nextNode != nil {
		curNode = curNode.nextNode
	}
	curNode.nextNode = node

	return singlyLinkedList
}

// 删除指定节点
func SinglyLinkedListDel(singlyLinkedList *SinglyLinkedListNode, data any) (*SinglyLinkedListNode, bool) {
	// 如果头节点为空，直接返回false
	if singlyLinkedList == nil {
		return singlyLinkedList, false
	}
	// 优先判断是否删除的是头节点，是则直接将头节点的下一个节点改为头节点返回
	if singlyLinkedList.data == data {
		return singlyLinkedList.nextNode, true
	}
	// 否则通过遍历找到要删除的节点，将要删除的节点的上一个节点指向要删除的节点的下一个节点
	curNode := singlyLinkedList
	for curNode.nextNode != nil {
		if curNode.nextNode.data == data {
			curNode.nextNode = curNode.nextNode.nextNode
			return singlyLinkedList, true
		}
		curNode = curNode.nextNode
	}
	return singlyLinkedList, false
}

// 打印链表元素
func SinglyLinkedListPrint(singlyLinkedList *SinglyLinkedListNode) {
	if singlyLinkedList == nil {
		fmt.Println("empty")
		return
	}
	curNode := singlyLinkedList
	for curNode.nextNode != nil {
		fmt.Printf("%+v", curNode)
		curNode = curNode.nextNode
	}
	fmt.Printf("%+v\n", curNode)
}

// 在指定节点之后插入
func SinglyLinkedListInsertAfter(singlyLinkedList *SinglyLinkedListNode, index, data any) (*SinglyLinkedListNode, bool) {
	if singlyLinkedList == nil {
		return singlyLinkedList, false
	}

	node := &SinglyLinkedListNode{data: data}

	curNode := singlyLinkedList
	for curNode != nil {
		if curNode.data == index {
			node.nextNode = curNode.nextNode
			curNode.nextNode = node
			return singlyLinkedList, true
		}
		curNode = curNode.nextNode
	}
	return singlyLinkedList, false
}

func SinglyLinkedListIsExist(singlyLinkedList *SinglyLinkedListNode, data any) bool {
	if singlyLinkedList == nil {
		return false
	}

	if singlyLinkedList.data == data {
		return true
	}

	curNode := singlyLinkedList
	for curNode.nextNode != nil {
		if curNode.nextNode.data == data {
			return true
		}
		curNode = curNode.nextNode
	}

	return false
}

func SinglyLinkedListLength(singlyLinkedList *SinglyLinkedListNode) int {
	length := 0
	curNode := singlyLinkedList
	for curNode != nil {
		length++
		curNode = curNode.nextNode
	}
	return length
}

func SinglyLinkedList_init() {
	fmt.Println("单向链表：")
	var singlyLinkedList *SinglyLinkedListNode
	ints := []int{1, 2, 3, 4, 5}
	for _, i := range ints {
		if i%2 == 0 {
			singlyLinkedList = SinglyLinkedListUnShift(singlyLinkedList, i)
		} else {
			singlyLinkedList = SinglyLinkedListPush(singlyLinkedList, i)
		}
	}
	SinglyLinkedListPrint(singlyLinkedList)
	// &{data:4 nextNode:0x140000be018}&{data:2 nextNode:0x140000be000}&{data:1 nextNode:0x140000be030}&{data:3 nextNode:0x140000be060}&{data:5 nextNode:<nil>}
	singlyLinkedList, _ = SinglyLinkedListDel(singlyLinkedList, 5)
	SinglyLinkedListPrint(singlyLinkedList)
	// &{data:4 nextNode:0x140000be018}&{data:2 nextNode:0x140000be000}&{data:1 nextNode:0x140000be030}&{data:3 nextNode:<nil>}
	singlyLinkedList, _ = SinglyLinkedListDel(singlyLinkedList, 2)
	SinglyLinkedListPrint(singlyLinkedList)
	// &{data:4 nextNode:0x140000be000}&{data:1 nextNode:0x140000be030}&{data:3 nextNode:<nil>}
	singlyLinkedList, _ = SinglyLinkedListInsertAfter(singlyLinkedList, 4, 2)
	SinglyLinkedListPrint(singlyLinkedList)
	// &{data:4 nextNode:0x140000be000}&{data:1 nextNode:0x140000be030}&{data:3 nextNode:<nil>}
	singlyLinkedList, _ = SinglyLinkedListInsertAfter(singlyLinkedList, 1, 5)
	SinglyLinkedListPrint(singlyLinkedList)
	// &{data:4 nextNode:0x140000be000}&{data:1 nextNode:0x140000be030}&{data:3 nextNode:<nil>}
	isExist := SinglyLinkedListIsExist(singlyLinkedList, 1)
	fmt.Printf("1 isExist %+v\n", isExist)
	// 1 isExist true
	isExist = SinglyLinkedListIsExist(singlyLinkedList, 8)
	fmt.Printf("8 isExist %+v\n", isExist)
	// 8 isExist false
	length := SinglyLinkedListLength(singlyLinkedList)
	fmt.Printf("length is %d\n", length)
	// length is 5
	SinglyLinkedListPush(singlyLinkedList, 8)
	length = SinglyLinkedListLength(singlyLinkedList)
	fmt.Printf("length is %d\n", length)
	// length is 6
	length = SinglyLinkedListLength(nil)
	fmt.Printf("length is %d\n", length)
	// length is 0
	SinglyLinkedListPrint(SinglyLinkedListPush(singlyLinkedList, 1))
	singlyLinkedList, _ = SinglyLinkedListDel(singlyLinkedList, 1)
	SinglyLinkedListPrint(singlyLinkedList)
}
